Systems, such as mechanical and/or electronic systems, are often analyzed to determine mathematical relationships among the system's inputs, states, and outputs. Once this information has been obtained, it can be used to create lookup tables that characterize the behavior of the system. A lookup table is a data structure, such as an array or associative array, which is often used to replace a runtime computation with a simpler array indexing operation.
Lookup tables can be generated by collecting input and output data for a static or dynamic system. This can be done artificially, via simulation, or experimentally by testing an actual system. In a system with M inputs and N outputs, a set of N, M-dimensional lookup tables can be used to characterize the behavior of the system. For a system with N output data values, N array elements are located and the corresponding data are stored at these locations.
Once a set of lookup tables is created based on system input and output data, it can be stored in computer memory so that the corresponding array of values can be used in applications without the need for regenerating the system output data. Only the input data is required to locate the appropriate array elements in the lookup table, and the approximate system output data can be read from these locations. As such, the use of lookup tables can provide a significant savings in terms of processing time since retrieving a value from memory is often faster than undergoing an extensive computation or input/output operation in real-time.
Lookup tables capture an input-output mapping of the system in the form of numeric data that can be stored at pre-determined array locations. A lookup table implements an array of table data (sometimes referred to as “elements”) and maps the table data/elements to a domain of indexed values at which the table has been evaluated for a given index. These indexed values serve to partition the table input space into regions referred to as “cells,” where each cell is delimited by two “breakpoints” to define an interval or segment into which an input value may fall.
A one-dimensional lookup table includes an index vector and a corresponding output vector. Each vector consists of a number of cells used to store values. The index vector comprises a set of discrete input values, and the output vector includes a series of corresponding output values such that each cell of the index vector is associated with a corresponding cell of the output vector. Each of the values of the index vector and the output vector are associated with or evaluated at a corresponding vector index which is typically an integer value.
In most cases, an input value into the lookup table can fall anywhere within a particular cell of the index vector (e.g., the input value may fall between two breakpoints that define a particular cell of an index vector). For a particular index vector, a search can be performed to identify the two cells of the index vector that are closest in value to the input value. For example, a processor determines the location of the input value relative to one of the intervals to identify the cells of the input vector and their corresponding numeric table data values.
Once the cells of the index vector have been identified, the corresponding cells of an output vector are known. The processor can then execute an interpolation algorithm based on the values of cells it has identified to interpolate between table data values to determine an output value that corresponds to the input value.
An index vector can be either linearly indexed or piecewise indexed. For a linearly index vector, the difference between any two consecutive cells is always the same. By contrast, for a piecewise indexed index vector, the index vector is indexed in a “piecewise” manner, meaning that cells are sometimes unevenly spaced such that a difference between one group of two consecutive cells of the piecewise indexed index vector is different than a difference between another group of two consecutive cells of the piecewise indexed index vector.
The method for searching the index vector to identify the cells of the index vector (that are closest in value to the input value) varies depending on whether the index vector is linearly indexed or piecewise indexed. For example, when the index vector is known to be linear, a search algorithm can be employed in which linear interpolation is calculated using the slope based on the difference between a group of two consecutive cells, and a computed index. By contrast, when the index vector is known to be piecewise indexed, a search algorithm can be employed in which the index vector is searched sequentially (i.e., on a cell-by-cell basis) from the beginning of the index vector until the index is found. This method for searching a piecewise indexed index vector consumes a significant amount of processor throughput.
Accordingly, it is desirable to provide improved methods and systems for searching an index vector of a lookup table for a vector index to identify the cells of the index vector that correspond to and are closest in value to the input value so that an output value (corresponding to the input value) can be determined. It would be desirable if these improved methods and systems can be used regardless of whether the index vector is linearly indexed or piecewise indexed. Furthermore, other desirable features and characteristics of the present invention will become apparent from the subsequent detailed description and the appended claims, taken in conjunction with the accompanying drawings and the foregoing technical field and background.